1. Field of the Invention
The present invention relates to creation of a network topology according to a directed acyclic graph for establishment of an ad hoc mobile network by mobile routers, and distribution of network traffic to a destination of the directed acyclic graph based on selecting from among multiple available paths in the directed acyclic graph.
2. Description of the Related Art
Proposals have been made by Internet Engineering Task Force (IETF) groups for improved mobility support of Internet Protocol (IP) based mobile devices (e.g., laptops, IP phones, personal digital assistants, etc.) in an effort to provide continuous Internet Protocol (IP) based connectivity. The IETF has a Mobile IP Working Group that has developed routing support to permit IP nodes (hosts and routers) using either IPv4 or IPv6 to seamlessly “roam” among IP subnetworks. In addition, the Mobile Networks (MONET) group (renamed as the Network Mobility (NEMO) group) has published different Internet Drafts, including an Internet Draft by Thierry Ernst, entitled “Network Mobility Support Terminology”, February 2002. An objective of NEMO is providing mobile nodes with protocols for establishing connectivity with a wide area network, such as the Internet. Thus, mobile routers have been used to establish a mobile network topology in order to route packets between the mobile network and the Internet via a gateway at an edge of the mobile network. However, such a mobile network topology typically requires an aggregate reachability to IP nodes, where all nodes sharing a common network link (such as a link of a top level mobile router connecting to an attachment router on the Internet) share the same routing prefix. Such aggregation creates a hierarchy of network prefixes that enables scalability. However, such a hierarchy is not possible in ad hoc networks.
The IETF has a Mobile Ad-hoc Networks (MANET) Working Group that is working to develop standardized MANET routing specification(s) for adoption by the IETF. According to the MANET Working Group, the “mobile ad hoc network” (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary graph. The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.
The MANET system is particularly suited to low-power radio networks that may exhibit an unstable topology, where wireless propagation characteristics and signal quality between a wireless transmission source and a receiver can be difficult to model and quantify. In a MANET, the device address is tied to the device, not a topological location, as there is no fixed network infrastructure. When the addressed device moves, therefore, the motion changes the routing infrastructure. Hence, as described in an Internet Draft by Baker, entitled “An Outsider's View of MANET” (Mar. 17, 2002), the fundamental behavior of a MANET is that a routing node carries with it an address or address prefix, and when it moves, it moves the actual address; when this happens, routing must be recalculated in accordance with the new topology. For example, each mobile router retains its address prefix; hence, neighboring mobile routers in a MANET may have distinct address prefixes.
FIG. 1 is a diagram illustrating a conventional layer 2 mesh network 10 having multiple mobile routers (N0, N1, N2, N3, N4) interconnected by links (A, B, C, D, E, F, G) having respective metrics (i.e., costs). The presence of layer 2 links (A, B, C, D, E, F, G), however, does not provide a routing topology that enables any given mobile router to reach a destination mobile router. Hence, a routing protocol such as Open Shortest Path First (OSPF) (as specified by the IETF Request for Comments (RFC) 2178) has been needed in order for each mobile router (e.g., N0) to determine a path to a given destination (e.g., N11).
Communications between mobile routers of an ad hoc network can be optimized based on the mobile routes organizing into a tree-based topology. For example, U.S. Patent Publication No. US 2004/0032852, published Feb. 19, 2004, entitled “Arrangement for Router Attachments Between Roaming Mobile Routers in a Mobile Network”, the disclosure of which is incorporated in its entirety herein by reference, describes a technique for each mobile router of an ad hoc mobile network to independently select whether to attach to a candidate attachment router, based on tree information options advertised by the candidate attachment router and selection criteria employed by the mobile router. The independent selection by each router of whether to attach to another router enables the routers to dynamically establish a tree-based network topology model, where each router may continually determine whether an alternate attachment point within the tree is preferred.
Link reversal routing has been suggested as a technique for providing multiple communications links between nodes in an ad hoc mobile network, where link reversal routing algorithms build a directed acyclic graph (DAG) for each possible destination: a directed graph is acyclic if it contains no cycle or loop, and the DAG maps to a given destination based on the destination having only incoming links: all other nodes that have incoming links also must have outgoing links. An example of a routing algorithm that builds a DAG is the Temporally-Ordered Routing Algorithm (TORA).
Commonly-assigned, copending application Ser. No. 11/167,240, filed Jun. 28, 2005, entitled “Directed Acyclic Graph Discovery and Network Prefix Information Distribution Relative to a Clusterhead in an Ad Hoc Mobile Network”, published Dec. 28, 2006 as U.S. Patent Publication No. 2006/0291404 (the disclosure of which is incorporated in its entirety herein by reference), describes one technique for creating a directed acyclic graph, where each mobile router in an ad hoc mobile network is configured for concurrently attaching to multiple parents advertising respective parent depths relative to a clusterhead of the ad hoc mobile network. The mobile router selects an advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths, enabling the mobile routers to form a directed acyclic graph relative to the clusterhead. Each mobile router sends to each of its parents a neighbor advertisement message specifying information that enables the parents to reach at least one reachable prefix relative to stored router entries.
Another example of a directed acyclic graph creation in an ad hoc network is described in commonly-assigned, copending application Ser. No. 11/251,765, filed Oct. 18, 2005, entitled “Directed Acyclic Graph Computation by Orienting Shortest Path Links and Alternate Path Links Obtained from Shortest Path Computation”, published Apr. 19, 2007 as U.S. Patent Publication No. 2007/0086358, the disclosure of which is incorporated in its entirety by reference. The network node performs a modified shortest path first calculation by identifying next-hop nodes adjacent to the network node, and orienting the link of each next-hop node toward itself (i.e., the origin). The network node also identifies secondary adjacent nodes, adjacent to each of the next hop nodes, and extends paths from next-hop nodes to the associated secondary adjacent nodes while orienting each of the links of the path between adjacent nodes and next-hop nodes toward the next hop nodes. The paths of the nodes form a directed acyclic graph from any other network node toward the origin, enabling distribution of the directed acyclic graph to the other network nodes for optimized reachability to the network node.
Although the foregoing description demonstrates that directed acyclic graphs can be readily created within an ad hoc network, a typical implementation would result in full utilization of the shortest path toward a DAG destination, with no utilization of any other path in the DAG until the shortest path was no longer available. Efforts to improve the performance of link state routing computations, also referred to Shortest Path First (SPF) based computations, based on using dynamic routing metrics instead of static metrics previously resulted in network instability. For example, in OSPF a router floods the network with link state advertisements (LSAs) advertising the assigned costs of the respective links utilized by the router, enabling other routers to calculate shortest routes to destinations. Use of dynamic routing metrics (e.g., early attempts at using dynamic routing metrics (e.g., in ARPANET)) were unsuccessful because the dynamic routing metrics tended to introduce instabilities due to oscillation in the link delay values: routers receiving an advertisement of a dynamic routing metric (e.g., a low link delay value in a delay-based routing protocol) would immediately reconfigure their routes to use the advertised low delay link, creating substantially higher traffic on the advertised link; routers would then reroute their paths around the advertised link that had become a high delay link, causing the router to advertise the advertised link again as a low delay link. Such oscillation in the dynamic routing metrics caused routing instability.
Load balancing technology has been implemented in conventional Internet Protocol based networks that have an established addressing hierarchy. For example Enhanced Interior Gateway Routing Protocol (EIGRP) (described in U.S. Pat. No. 5,519,704 and incorporated in its entirety herein by reference) permits unequal-cost load balancing. However, EIGRP is a distance vector-based routing protocol and therefore incompatible with OSPF-based routing protocols, and therefore cannot be used in networks that rely on directed acylic graphs.
Other proposals such as Reservation Protocol with Traffic Engineering (RSVP-TE) according to RFC 3209 require best paths to be regularly recomputed using Constrained Shortest Path First (CSPF) (RFC 4105), which causes a loss of routing capabilities until the new best paths have been established. In addition, such proposals require source-route capabilities, which introduces the necessity of maintaining path states throughout a path in the network.